package Leetcode第二期;

import java.time.chrono.MinguoDate;

/**
 * @author : K k
 * @date : 15:06 2020/10/2
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 *  
 *
 * 示例:
 *
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true
 * 给定 word = "SEE", 返回 true
 * 给定 word = "ABCB", 返回 false
 */
public class 单词搜索_79 {
    boolean[][] visit;

    //方法1：dfs官方
    public boolean exist(char[][] board, String word) {
        int n=board.length;
        int m=board[0].length;
        visit=new boolean[n][m];
        boolean flag=false;
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if (board[i][j]==word.charAt(0)){
                    //找到开头进行搜索
                    flag=dfsSolver(board,word,i,j,n,m,0);
                    if (flag){
                        return flag;
                    }
                }
            }
        }
        return flag;
    }

    private boolean dfsSolver(char[][] board, String word, int i, int j, int n, int m, int index) {
        if (board[i][j] != word.charAt(index)){
            return false;
        }
        else if (index==word.length()-1){
            return true;
        }
        visit[i][j] = true;

        //三个方向：右，下，左
        int[][] direction=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        boolean result = false;
        for (int p = 0; p < 4; p++) {
            int newi = i + direction[p][0], newj = j + direction[p][1];
            if (isArea(board,newi,newj,n,m)&&visit[newi][newj]==false) {
                //三个方向
                boolean check=dfsSolver(board,word,newi,newj,n,m,index+1);
                if (check){
                    result=true;
                    break;
                }
            }
        }
        visit[i][j]=false;
        return result;
    }

    private boolean isArea(char[][] board, int i, int j, int n, int m) {
        return i>=0 && i<n && j>=0 && j<m;
    }


    //方法2：dfs
    /*//三个方向：右，下，左
    int[][] direction=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    boolean[][] visit;
    boolean flag=false;

    public boolean exist(char[][] board, String word) {
        int n=board.length;
        int m=board[0].length;
        visit=new boolean[n][m];
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if (board[i][j]==word.charAt(0)){
                    //找到开头进行搜索
                    dfsSolver(board,word,i,j,n,m,0);
                    if (flag){
                        return flag;
                    }
                }
            }
        }
        return flag;
    }

    private void dfsSolver(char[][] board, String word, int i, int j, int n, int m, int index) {
        if (index==word.length()){
            flag=true;
            return;
        }

        if (isArea(board,i,j,n,m)&&visit[i][j]==false) {
            if (board[i][j] == word.charAt(index)) {
                //进行搜索
                visit[i][j] = true;
                for (int p = 0; p < 4; p++) {
                    if(flag==true){
                        break;
                    }
                    //三个方向
                    dfsSolver(board,word,i+direction[p][0],j+direction[p][1],n,m,index+1);
                }
                visit[i][j]=false;
            }
        }
    }

    private boolean isArea(char[][] board, int i, int j, int n, int m) {
        return i>=0 && i<n && j>=0 && j<m;
    }*/
    public static void main(String[] args) {
        单词搜索_79 x=new 单词搜索_79();
        System.out.println(x.exist(new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        }, "ABCCED"));
    }
}
